package leetcode.sword;

public class Solution03 {
    public int findRepeatNumber1(int[] nums) {
        //把每个数字i放到该在的位置i上，如果发现那个位置上已经放了一个i,说明i重复了
        int i = 0;
        while(i<nums.length){
            //如果位置i数字就是i,往下走
            if(i==nums[i]) {
                i++;
                continue;
            }
            //不是i，就把i为索引的数字和nums[i]为索引的数字交换，这样至少nums[i]处的数字排好了为i
            int tmp = nums[i];
            //判断nums[i]为索引的地方存放的是不是已经存了正确的值
            if(nums[tmp]==tmp) return tmp;
            //如果没有存好，让索引i和索引tmp交换数字，把tmp处的数字放好
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return 0;
    }

    public int findRepeatNumber(int[] nums){
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            //先检查i位置数字对不对
            if(nums[i]==i) continue;
            //i位置没有放i，往后排
            int j = nums[i];
            nums[i] = -1; //防止死循环
            while (j>=0&&j!=nums[j]){
                int tmp = nums[j];
                nums[j] = j;
                j = tmp;
            }
            //位置j放了j，不能再往上放了，重复
            if(j>=0) return j;
        }
        return 0;
    }
}
